package org.example.myleet.p1365;

import java.util.Arrays;

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        //深拷贝，构建答案用
        int[] copy = Arrays.copyOf(nums, nums.length);
        //答案数组
        int[] answer = new int[nums.length];
        //缓存答案用的槽
        int[] slot = new int[101];
        //排序
        Arrays.sort(copy);
        //最小的数字，不大于数组中其他数字，为0
        int min = copy[0];
        slot[copy[0]] = 0;
        for (int i=1; i<copy.length; i++) {
            if (copy[i] > min) {
                //此数字大于当前最小数字，则前面的数字都小于这个数，位置即是个数
                slot[copy[i]] = i;
                //更新当前最小数字
                min = copy[i];
            } else {
                //不能大于前面的数字，沿用上一个数字大于的数字个数
                slot[copy[i]] = slot[copy[i-1]];
            }
        }
        for (int i=0; i<nums.length; i++) {
            //利用槽缓存的答案组装输入顺序的答案
            answer[i] = slot[nums[i]];
        }
        return answer;
    }
}
